« Previous Next »

Minimax - los de puzzel op

Je hebt gezien dat een evaluatiefunctie een beeld kan geven van de huidige toestand in een game. Speler 1 wil graag een hoge score en speler 2 wil graag een lage score. Een simpele werkwijze zou kunnen zijn:

• Probeer elke zet uit.
• Kijk bij elke zet hoe het bord er uit komt te zien.
• Doe de zet waarbij het bord er het beste uit ziet voor jou.

Dit werkt een beetje, maar niet erg goed. Wat we willen is dat de AI verder vooruit denkt dan 1 zet. Daarvoor wordt het minimax algoritme gebruikt. Bij minimax wordt de volgende vraag gesteld:

"Als ik alle combinaties van zetten voor de komende X beurten uitprobeer en ik neem aan dat beide spelers perfect spelen, welke zet kan ik dan het beste doen?"

Hierbij hangt X af van de rekenkracht van de computer. Hoe meer rekenkracht hoe dieper je kunt gaan in de beslisboom. Bekijk bijvoorbeeld onderstaand plaatje:

Dit is een klein stukje van de gehele beslisboom van boter, kaas en eieren. De volledige beslisboom bevat 26830 borden. De beslisboom is maximaal 9 beurten diep (waarom?). Een computer kan met gemak de hele beslisboom doorrekenen en het minimax algoritme gebruiken om de beste zet te kiezen. Hieronder zie je een voorbeeld van minimax in een Boter, kaas en eieren AI. Probeer maar eens te winnen. Je speelt om de beurt kruisje of rondje. 

Het minimax algoritme is recursief en dat betekent dat het zichzelf aanroept. We beginnen bovenaan de boom en het werkt als volgt:

• Maak een lijst met zetten
• Probeer elke zet uit en roep voor elke nieuwe situatie opnieuw de minimax functie aan. 
• Ben je speler 1, kies dan de zet met de hoogste minimax-score. Ben je speler 2, kies de zet met de laagste minimax-score. 

Omdat minimax iedere keer zichzelf aanroept, lijkt er geen einde aan te komen. Dat is niet waar. Het zichzelf aanroepen van het minimax-algoritme kan op twee manieren eindigen:

1) Het spel is voorbij en er is een eindresultaat (verloren, gewonnen of gelijk). De scores die hierbij horen zijn bijvoorbeeld -100, 100 en 0.

2) We zijn tot de maximum-diepte gekomen. Dit maximum hangt meestal af van de beschikbare rekentijd. In dit geval bepalen we de score met een evaluatiefunctie.

Opdracht: Los de minimax puzzel op. Alle mogelijke combinaties van zetten voor de komende 4 beurten van een spel, zijn weergegeven. Speler 1 is aan de beurt en wil zo hoog mogelijk scoren. Zoek uit welke zet speler 1 moet doen (A, B, C of D) en wat de maximale score is die speler 1 kan halen, aangenomen dat speler 2 perfect speelt. De evaluatiescores op alle plekken waar de boom eindigt, zijn weergegeven.

Link naar puzzel